package ahu.zdw.com;

import java.util.Stack;

/**
 * Author: Zhang Dongwei
 * Date: 2021/12/19 19:54
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 注释：参考了其他博主的答案：https://blog.csdn.net/dadongwudi/article/details/108029527
 */
public class _20_IsValid {
    public static void main(String[] args) {
        Solution solution = new _20_IsValid().new Solution();
        boolean res = solution.isValid("[]{()[]}[{}]");
        System.out.println(res);

    }

    class Solution {
        public boolean isValid(String s) {
            int l = s.length();
            if(l==0 || s.equals(null)){
                return true;
            }
            Stack<Character> stack = new Stack<Character>();
            for(int i=0; i<l; i++){
                char a = s.charAt(i);

                if(a=='('){
                    stack.push(')');
                }else if (a=='['){
                    stack.push(']');
                }else if (a=='{'){
                    stack.push('}');
                }else if(stack.isEmpty() || stack.pop()!=a){
                    return false;
                }
            }
            return stack.isEmpty();
        }
    }

}
